package com.ssh;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class RestoreIpAddresses_93 {
	public List<String> restoreIpAddresses(String s) {
		List<String> list = new ArrayList<String>();
        if (s.length()<4 || s.length()>12) {
        	return list;
        }
        dfs(list, new StringBuilder(), s, 0);
        return list;
    }
	
	public void dfs(List<String> list, StringBuilder sb, String s, int x) {
		String s1 = sb.toString();
		if (s1.replace(".", "").length() == s.length()&&sb.length() == s.length()+4) {
			sb.delete(sb.lastIndexOf("."), sb.lastIndexOf(".")+1);
			list.add(sb.toString());
			return;
		}
		for(int i = 3; i > 0; i--) {
			if ((x+i) <= s.length()) {
				String st = s.substring(x, x+i);
				if (Integer.parseInt(st)<=255) {
					sb.append(Integer.parseInt(st)+".");
					dfs(list, sb, s, x+i);
					sb.delete(sb.lastIndexOf(String.valueOf(Integer.parseInt(st))), sb.length());
				}
			}
		}
	}
	
	
	@Test
	public void test() {
		List<String> list = restoreIpAddresses("010010");
		System.out.println(list.toString());
	}

}
